package binary_search;

/**题目：旋转有序数组的搜索
 * y: [4,5,6,7,1,2,3]
 * @Author Gavin
 * @date 2022.01.18 22:21
 */
public class array_4 {
    /**
     * 解题思路：采用二分搜索法
     * 我们需要了解到这个数组的特点，原数组是递增的，
     * 首先计算出来的mid值有两种情况，如果mid值大于low值的话说明mid值左边的的所有数
     * 都是递增的（因为旋转之前的数组是递增的）。
     * 如果mid小于low值的话说明mid值就落在了旋转的那部分值里面了（旋转的那部分值的最大值都要小于low）
     */
    public int solution(int[] nums,int target){
        if(nums==null||nums.length==0)return -1;
        int low=0,high=nums.length-1;
        while (low<=high){
            int mid=low+(high-low)/2;
            if(target==nums[mid])return mid;
            if(nums[mid]>=nums[low]){//正常的情况
                if(target<nums[mid])high=mid-1;
                else low=mid+1;
            }else{//处理旋转的部分
                if(target>nums[mid]&&target<=nums[high])low=mid+1;
                else high=mid-1;
            }
        }
        return -1;
    }
}
